﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using Xceed.Silverlight.Data.Stats;

namespace Xceed.Silverlight.Data
{
  internal class ListDataItemIndex
  {
    #region Constructor

    internal ListDataItemIndex(
      ListDataItemCollection dataSource,
      ListDataItemIndexConfiguration configuration )
    {
      if( dataSource == null )
        throw new ArgumentNullException( "dataSource" );

      if( configuration == null )
        throw new ArgumentNullException( "configuration" );

      m_configuration = configuration;

      IEnumerable<RawDataItem> itemsSource;
      Func<RawDataItem, bool> predicate = configuration.CreatePredicate();
      // Remove the items that must not be part of the index.
      itemsSource = ListDataItemIndex.Filter( dataSource, predicate );
      // Sort the items according to the sort order.
      itemsSource = ListDataItemIndex.Sort( itemsSource, configuration.SortOrder );
      m_dataSource = itemsSource.ToList();

      IEqualityComparer<StatFunction> statFunctionComparer = new StatFunctionEqualityComparer();
      m_root = ListDataItemIndex.CreateIndex( m_dataSource, configuration, statFunctionComparer );
    }

    #endregion

    #region Configuration Property

    internal ListDataItemIndexConfiguration Configuration
    {
      get
      {
        return m_configuration;
      }
    }

    private ListDataItemIndexConfiguration m_configuration;

    #endregion

    #region ItemsCount Property

    internal int ItemsCount
    {
      get
      {
        return m_dataSource.Count;
      }
    }

    #endregion

    internal void Add( RawDataItem dataItem )
    {
      if( dataItem == null )
        return;

      // Make sure the data item should be added to the index.
      Func<RawDataItem, bool> predicate = m_configuration.CreatePredicate();
      if( ( predicate != null ) && ( !predicate.Invoke( dataItem ) ) )
        return;

      int index = m_dataSource.BinarySearch( dataItem, m_configuration.ItemComparer );
      if( index < 0 )
      {
        index = ~index;
      }

      m_dataSource.Insert( index, dataItem );

      // Repair the the tree.
      if( m_root != null )
      {
        IEnumerable<object> groupValues = ( from sort in m_configuration.SortOrder
                                            select dataItem.GetDataMemberValue( sort.PropertyName ) );
        LinkedList<object> groupValue = new LinkedList<object>( groupValues );

        m_root.Add( groupValue.First );
      }
      // We only have one item in the index.
      else
      {
        IEqualityComparer<StatFunction> statFunctionComparer = new StatFunctionEqualityComparer();
        m_root = ListDataItemIndex.CreateIndex(
                   m_dataSource,
                   m_configuration,
                   statFunctionComparer );
      }

      // Any enumerable on the index should be discarded.
      m_version++;
    }

    internal void Remove( RawDataItem dataItem )
    {
      if( dataItem == null )
        return;

      // We must check if the item is in the index even if it doesn't pass the configuration 
      // filter predicate right now since a property change may have occured.
      int index = m_dataSource.BinarySearch( dataItem, m_configuration.ItemComparer );
      if( index < 0 )
      {
        // The item may not be sorted anymore if it has changed.
        // We must look for it item by item.
        index = m_dataSource.IndexOf( dataItem );

        // The item doesn't seem to be in the data source at all.
        if( index < 0 )
          return;
      }

      m_dataSource.RemoveAt( index );

      Debug.Assert( m_root != null );

      // We must remove the root node if there is no more item in the collection.
      if( m_root.Remove( index ) )
      {
        m_root = null;
      }

      // Any enumerable on the index should be discarded.
      m_version++;
    }

    internal ListDataItemEnumerable GetDataItems( bool reverseOrder )
    {
      // Determine the desired range.
      int startIndex = 0;
      int length = m_dataSource.Count;
      int totalCount = length;

      if( reverseOrder )
      {
        startIndex = length - 1;
        length = -length;
      }

      // Retrieve an enumerator on the desired items.
      IEnumerable<RawDataItem> dataItems = this.GetDataItems( startIndex, length );

      return new ListDataItemEnumerable( dataItems, totalCount, totalCount );
    }

    internal ListDataItemEnumerable GetDataItems(
      IEnumerable<object> startingValues,
      bool reverseOrder )
    {
      return this.GetDataItems( startingValues, reverseOrder, false );
    }

    internal ListDataItemEnumerable GetDataItems(
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( m_root == null )
        return ListDataItemEnumerable.Empty();

      if( !startingValues.Any() )
        return this.GetDataItems( reverseOrder );

      LinkedList<object> groupValues = new LinkedList<object>( startingValues );

      // Get the index of the first item to return.
      int startIndex = m_root.GetDataItemIndex( groupValues.First, reverseOrder, skipStartingItem );
      int totalCount = m_dataSource.Count;

      // We are out of bound, there is no item to return.
      if( ( startIndex < 0 ) || ( startIndex >= totalCount ) )
        return ListDataItemEnumerable.Empty( totalCount );

      int length = ( reverseOrder )
                     ? -( startIndex + 1 )
                     : totalCount - startIndex;

      // Retrieve an enumerator on the desired range.
      IEnumerable<RawDataItem> dataItems = this.GetDataItems( startIndex, length );

      return new ListDataItemEnumerable( dataItems, Math.Abs( length ), totalCount );
    }

    internal IEnumerable<int> GetGroupCount( int levelCount )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        m_root.GetGroupCount( groupCount.First );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> groupValues = new LinkedList<object>( startingValues );
        m_root.GetGroupCount( groupCount.First, groupValues.First );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues,
      bool reverseOrder )
    {
      return this.GetGroupCount( levelCount, startingValues, reverseOrder, false );
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> groupValues = new LinkedList<object>( startingValues );
        m_root.GetGroupCount( groupCount.First, groupValues.First, reverseOrder, skipStartingItem );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> groupValues,
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> filterGroupValues = new LinkedList<object>( groupValues );
        LinkedList<object> groupStartingValues = new LinkedList<object>( startingValues );

        m_root.GetGroupCount(
          groupCount.First,
          filterGroupValues.First,
          groupStartingValues.First,
          reverseOrder,
          skipStartingItem );
      }

      return groupCount;
    }

    internal void ClearStatResults()
    {
      if( m_root != null )
      {
        m_root.ClearStatResults();
      }
    }

    internal StatResult GetStatValue( 
      StatFunction statFunction, 
      IEnumerable<object> groupValues )
    {
      if( ( m_root == null ) || ( statFunction == null ) )
        return null;

      LinkedListNode<object> firstGroupValue = null;

      if( ( groupValues != null ) && ( groupValues.Any() ) )
        firstGroupValue = ( new LinkedList<object>( groupValues ) ).First;

      return m_root.GetStatValue( statFunction, firstGroupValue );
    }

    internal void SetStatValue(
      StatFunction statFunction,
      IEnumerable<object> groupValues,
      StatResult statResult )
    {
      if( ( m_root == null ) || ( statFunction == null ) )
        return;

      LinkedListNode<object> firstGroupValue = null;

      if( ( groupValues != null ) && ( groupValues.Any() ) )
        firstGroupValue = ( new LinkedList<object>( groupValues ) ).First;

      m_root.SetStatValue( statFunction, firstGroupValue, statResult );
    }

    private IEnumerable<RawDataItem> GetDataItems( int startIndex, int length )
    {
      return this.GetDataItems( startIndex, length, m_version );
    }

    private IEnumerable<RawDataItem> GetDataItems( int startIndex, int length, int version )
    {
      if( length == 0 )
        yield break;

      int index = startIndex;
      int step = Math.Sign( length );
      int count = Math.Abs( length );

      while( true )
      {
        // Make sure the data list has changed since the last enumerated value.
        if( version != m_version )
          throw new InvalidOperationException( "An attempt was made to retrieve the data items from a data source that has changed." );

        // We've enumerable all the desired values or the end of the source has been reached.
        if( ( count <= 0 ) || ( index < 0 ) || ( index >= m_dataSource.Count ) )
          yield break;

        // Return the desired item.
        yield return m_dataSource[ index ];

        index += step;
        count--;
      }
    }

    private static Func<LinkedListNode<object>, int, ListDataItemIndexNode> GetBranchCreator(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer )
    {
      int levelCount = configuration.SortOrder.Count;

      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator = null;
      branchCreator =
        ( groupValues, indexStart ) =>
        {
          // Find out at which level we are now.
          int level = levelCount;
          LinkedListNode<object> levelValue = groupValues;
          while( levelValue != null )
          {
            level--;
            levelValue = levelValue.Next;
          }

          // We are on the last level.
          if( level >= configuration.SortOrder.Count - 1 )
            return new ListDataItemIndexLeaf( configuration, statFunctionComparer, level, indexStart, 1, dataSource.BinarySearch );

          ListDataItemIndexNode childContainer = branchCreator.Invoke( groupValues.Next, indexStart );
          ListDataItemIndexGroup childGroup = new ListDataItemIndexGroup( groupValues.Value, childContainer );

          return new ListDataItemIndexGroupContainer(
            configuration,
            statFunctionComparer,
            level,
            indexStart,
            1,
            new ListDataItemIndexGroup[] { childGroup },
            branchCreator );
        };

      return branchCreator;
    }

    private static ListDataItemIndexNode CreateIndex(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer )
    {
      // There is no index to create if there is no data.
      if( dataSource.Count <= 0 )
        return null;

      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator = ListDataItemIndex.GetBranchCreator(
                                                                                 dataSource,
                                                                                 configuration,
                                                                                 statFunctionComparer );

      return ListDataItemIndex.CreateLevel(
        dataSource,
        configuration,
        statFunctionComparer,
        0,
        0,
        dataSource.Count,
        branchCreator );
    }

    private static ListDataItemIndexNode CreateLevel(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer,
      int level,
      int startIndex,
      int length,
      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator )
    {
      // We are on the leaf level.
      if( level >= configuration.SortOrder.Count - 1 )
        return new ListDataItemIndexLeaf( 
                 configuration, 
                 statFunctionComparer, 
                 level, 
                 startIndex, 
                 length, 
                 dataSource.BinarySearch );

      string memberName = configuration.SortOrder[ level ].PropertyName;
      List<ListDataItemIndexGroup> childGroups = new List<ListDataItemIndexGroup>();

      // Regroup the items that share the same group value.
      int endIndex = Math.Min( startIndex + length, dataSource.Count );
      int i = startIndex;
      while( i < endIndex )
      {
        object groupValue = dataSource[ i ].GetDataMemberValue( memberName );
        int groupLength = 0;

        // Find out the number of items that are part of the same group.
        for( int j = i; j < endIndex; j++ )
        {
          // Check if a new group has begun.
          if( !object.Equals( dataSource[ j ].GetDataMemberValue( memberName ), groupValue ) )
            break;

          groupLength++;
        }

        // Create the children groups.
        ListDataItemIndexNode childContainer = ListDataItemIndex.CreateLevel(
                                                 dataSource,
                                                 configuration,
                                                 statFunctionComparer,
                                                 level + 1,
                                                 i,
                                                 groupLength,
                                                 branchCreator );
        if( childContainer != null )
        {
          ListDataItemIndexGroup childGroup = new ListDataItemIndexGroup( groupValue, childContainer );
          childGroups.Add( childGroup );
        }

        i += groupLength;
      }

      // Create the main container.
      return new ListDataItemIndexGroupContainer(
        configuration,
        statFunctionComparer,
        level,
        startIndex,
        length,
        childGroups,
        branchCreator );
    }

    private static IEnumerable<TElement> Filter<TElement>(
      IEnumerable<TElement> source,
      Func<TElement, bool> predicate )
    {
      if( predicate == null )
        return source;

      return source.Where( predicate );
    }

    private static IEnumerable<TElement> Sort<TElement>(
      IEnumerable<TElement> source,
      IEnumerable<SortDescription> sortOrder ) where TElement : RawDataItem
    {
      if( !sortOrder.Any() )
        return source;

      bool isFirstDescription = true;
      IOrderedEnumerable<TElement> result = null;

      foreach( SortDescription sort in sortOrder )
      {
        string memberName = sort.PropertyName;
        bool isAscending = ( sort.Direction == ListSortDirection.Ascending );

        Func<TElement, object> keySelector = ( TElement item ) =>
        {
          return item.GetDataMemberValue( memberName );
        };

        if( isFirstDescription )
        {
          isFirstDescription = false;
          result = ( isAscending )
                     ? source.OrderBy( keySelector )
                     : source.OrderByDescending( keySelector );
        }
        else
        {
          result = ( isAscending )
                     ? result.ThenBy( keySelector )
                     : result.ThenByDescending( keySelector );
        }
      }

      return result;
    }

    #region Private Fields

    private ListDataItemIndexNode m_root; //null
    private List<RawDataItem> m_dataSource; //null
    private int m_version; //0

    #endregion

    #region Private StatFunctionEqualityComparer Nested Type

    private class StatFunctionEqualityComparer : IEqualityComparer<StatFunction>
    {
      public int GetHashCode( StatFunction obj )
      {
        if( obj == null )
          return 0;

        return obj.GetEquivalenceKey();
      }

      public bool Equals( StatFunction x, StatFunction y )
      {
        return StatFunction.AreEquivalents( x, y );
      }
    }

    #endregion
  }
}
